Automated problem solvers are widely used in the resolution of complex, NP-difficult or NP-hard problems. Such problems arise frequently in industrial applications, for example planning, scheduling and configuration problems. Typical examples include supply chain optimization, planning delivery routes for goods, software verification, logistics of large conference scheduling, and data center energy profile management. An example of a problem solver engine is Microsoft™ Solver Foundation.
Such problems are defined in terms of variables and relations between the variables in the form of constraints. The problem solver searches for possible solutions by searching for values for all the variables that satisfy the constraints. The problem solver typically solves the problem by creating a tree data structure representing the variables, pruning the tree according to the constraints and searching the tree for a solution.
One of the characteristics of such problem solvers is a high runtime variance. This variance comes from the sensitivity of the resolution to the problem solver's parameters. Ideally, a problem solver is run with the optimum parameters for a given problem to ensure the shortest runtime and high overall performance. However, it is very difficult to know before-hand which parameters ought to be used with a particular problem. One way to address this is to run several parallel problem solvers with different parameters, such that the first problem solver to finish delivers the solution and stops the other search efforts.
Parallel problem solvers can also be used to improve performance by splitting up the tree in order to create a number of independent sub-problems. Each of these sub-problems can be solved in parallel, and ultimately combined together to provide the overall result. Parallel problem solvers have become increasingly used since the widespread adoption of multi-core processors.
When parallel problem solvers are being utilized (each either addressing the same problem with different parameters or addressing related sub-problems), the performance can be further improved by enabling the parallel problem solvers to exchange information on the search process. This is often called “knowledge sharing”.
For example, problem solving algorithms can learn new constraints as the problem is solved, and add these new constraints to the ones defined by the user. The learning of new constraints makes the problem easier to solve. It is therefore useful to share these learnt constraints between the parallel problem solvers, so that the other problem solvers running in parallel also benefit from knowledge of these constraints.
However, the process of communicating the information between the problem solvers can slow down the resolution of the problem. This is because the process of selecting, exchanging and integrating information interrupts the search process, and is thus time consuming and causes overheads.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known problem solvers.